1. Field of the Invention
The present invention relates to a coding device for an image signal having gradation.
2. Description of the Related Art
In handling an image having gradation in an image processing device or the like, image information is generally coded to thereby compress an amount of information, because digitization of the original image information brings about a large amount of information.
While various methods for coding an image signal are known, a transform coding system is known as a typical coding method for an image having gradation.
Generally, in an image called a natural image such as a landscape picture and a portrait picture, it is known that adjacent pixels tend to have near pixel values and show a high correlativity. Such a high correlativity of signals as viewed on an axis of frequency means a concentrated distribution of signal power in a low-frequency component. By coding only the low-frequency component where the signal power is concentrated, the total amount of information can be reduced.
The transform coding system uses this property in such a manner that a large number of bits are allocated to a low-frequency component where the signal power is concentrated and a small number of bits are allocated to a high-frequency component where the signal power is not concentrated, thus reducing the total amount of information.
The JPEG (Joint Photographic Expert Group) system known as an international standard system for still picture coding as disclosed in G. K. Wallace: "The JPEG Still Picture Compression Standard", Communications of the ACM (April, 1991) adopts an algorithm based on Discrete Cosine Transform (which will be hereinafter abbreviated to DCT) as one kind of the transform coding system.
The configuration of the transform coding system will now be described with reference to FIG. 9 showing a fundamental block diagram.
Referring to FIG. 9, reference numeral 100 denotes a DCT section for performing DCT to each of plural pixel blocks obtained by dividing an image into rectangular pixel regions to generate a transform coefficient of a spatial frequency component; reference numeral 101 denotes a linear quantization section for linearly quantizing the transform coefficient by using a quantization threshold set in a quantization matrix 102 to generate a quantized coefficient; and reference numeral 103 denotes a variable length coding section for coding the quantization coefficient by using a Huffman code table 104 to generate code data.
The coding operation will now be described with reference to FIG. 9.
In the DCT section 100, each pixel block consisting of 8.times.8 pixels as a rectangular region is subjected to DCT. Eight-degree two-dimensional DCT is given by Eq. (1), and inverse transform is given by Eq. (2). ##EQU1## where f(j,k) represents each element of the pixel block, and j and k represent a position of each element; and F(u,v) represents each element of the transform coefficient, and u and v represent a position of each element.
FIG. 10A shows an example of the pixel block consisting of 8.times.8 pixels input into the DCT section 100. FIG. 10B shows all elements of the transform coefficient obtained by performing the eight-degree two-dimensional DCT given by Eq. (1) to all pixels in the pixel block. As shown in FIG. 11, the left uppermost element of the matrix of the transform coefficient corresponds to an average brightness of the pixel blocks, and it is accordingly called a DC coefficient. The other elements except the DC coefficient are called an AC coefficient.
As shown in FIG. 11, the righter the column of the elements of the AC coefficient, the higher the frequency component in the horizontal direction, and the lower the row of the elements of the AC coefficient, the higher the frequency component in the vertical direction. That is, the right lowermost element of the matrix of the AC coefficient corresponds to the maximum frequency component in the horizontal and vertical directions.
The transform coefficient generated from the DCT section 100 is quantized in the linear quantization section 101 and is generated as the quantized coefficient therefrom. The quantization is a processing of dividing each element of the transform coefficient by the corresponding element of the quantization matrix to obtain a quotient, and is defined by the following expressions. EQU F.sup.Q (u,v)=(F(u,v)+(Q(u,v))/2))Q(u,v) (F(u,v).gtoreq.0) (4) EQU F.sup.Q (u,v)=(F(u,v)-(Q(u,v))/2))Q(u,v) (F(u,v)&lt;0) (5)
where F(u,v), Q(u,v), and F.sup.Q (u,v) represent each element of the transform coefficient, each element of the quantization matrix, and each element of the quantized coefficient, respectively, and u and v represent a position of each element.
FIG. 10C shows an example of the quantization matrix decided in consideration of visual characteristics of each frequency component. In a natural image, the signal power is concentrated at a low-frequency coefficient. Therefore, as shown in FIG. 10C, it is general that the transform coefficient corresponding to a low-frequency component is precisely quantized by using a small value and that the transform coefficient corresponding to a high-frequency component is roughly quantized by using a large value.
FIG. 12A shows a quantized coefficient obtained by linearly quantizing the transform coefficient shown in FIG. 10B by using the quantization matrix shown in FIG. 10C.
The quantized coefficient generated from the linear quantization section 101 is coded by Huffman coding in the variable length coding section 103. The Huffman code table 104 is used for both the DC component and the AC component, and the coding of both components is individually performed.
The coding of the DC coefficient will now be described. First, a difference in DC coefficient between the current block and the immediately previous block is obtained, and a plurality of group numbers are decided according to all differences obtained as shown in FIG. 13. Then, the group numbers are coded by Huffman coding. Further, a plurality of overhead bits each having the same number of bits as the corresponding group number are added, so as to indicate the correspondence between the difference and the group number.
It is assumed that the DC component in the immediately previous block with respect to the quantized coefficient shown in FIG. 12A is 14, the difference in DC component between the current block and the immediately previous block is given by 16-14=+2. In this case, it is understood from FIG. 13 that the group number is 2. Further, it is understood from FIG. 14 showing the Huffman code table for the DC component that the code corresponding to the group number "2" is a binary code "011". Further, in order to identify four values of -3, -2, 2, and 3 belonging to the group number "2", 2-bit information is added In case of identifying the value "2", 2-bit information "10" is added.
The coding of the AC coefficient will now be described.
The AC coefficient is made one-dimensional by zigzag scanning the matrix shown in FIG. 2 in the numerical order of 1 to 63. In this zigzag scanning, a length of continuation (zero run) of a zero coefficient (ineffective coefficient) is counted until a non-zero coefficient (effective coefficient) appears. When the effective coefficient appears, a group number corresponding to the AC coefficient is decided as shown in FIG. 15. Further, overhead bits indicating the correspondence between the AC coefficient and the group number are also decided as shown in FIG. 15.
In the Huffman code table for the AC coefficient, Huffman codes are allocated to the combinations of the zero runs of the ineffective coefficient and the group numbers of the effective coefficient subsequent to the ineffective coefficient. FIG. 16 shows the combinations of the zero runs of the ineffective coefficient and the group numbers of the effective coefficient, that is, 256 combinations of (0,0) to (15,15). All the combinations are correspondingly given binary codes as shown in FIGS. 17 and 18.
Thus, all elements of the AC coefficient are coded with the combinations of the zero runs of the ineffective coefficient and the group numbers of the effective coefficient subsequent to the ineffective coefficient and with the overhead bits indicating the correspondence between the effective coefficient and the group number. Until all elements of the effective coefficient in each block are completely processed, the above operation is repeated. Further, when the remaining elements of the AC coefficient in each block are identified as all zero, and an EOB (block end code) is coded at this time to end the processing of one block.
FIG. 19 shows an example of the coding of the quantized coefficient shown in FIG. 12A in accordance with the above procedure, and FIG. 20 shows a bit string to be output as a code. The information of 512 bits that are all bits in one block consisting of 8.times.8 pixels each formed by 8 bits is compressed to 63 bits as all bits.
In decoding the image information, Huffman decoding is performed in the reverse procedure of the above to reproduce the quantized coefficient shown in FIG. 12A. Then, each element of the quantized coefficient is multiplied by the corresponding element of the quantization matrix shown in FIG. 10C to thereby obtain a dequantized coefficient shown in FIG. 12B. Then, the dequantized coefficient obtained is subjected to the inverse DCT expressed by Eq. (2) to thereby obtain a reconstructed pixel block shown in FIG. 12C.
Thus, the image information can be coded and decoded by performing the above processings in accordance with the transform coding system.
However, in quantizing the transform coefficient by using the transform coding system, all elements of the transform coefficient corresponding to all pixels are divided by the respective quantization thresholds, thus requiring much time for computation of quantization to render an operating speed slow.
A method for attaining a high-speed operation of quantization is disclosed in Japanese Patent Laid-open No. Hei 3-262381. In the image data coding method and device described in this literature, some of the elements of the transform coefficient that become zero after DCT are detected before quantization, and the division of these zero elements is omitted to thereby reduce an amount of computation.
The configuration of the system disclosed in the above literature will now be described with reference to FIG. 21.
Referring to FIG. 21, reference numeral 310 denotes transform coefficient holding means for temporarily holding a transform coefficient; reference numeral 320 denotes effective address detecting means for scanning all elements of the transform coefficient in each block held in the transform coefficient holding means 310 and detecting an effective address; reference numeral 330 denotes quantization means for quantizing the transform coefficient held in the transform coefficient holding means 310 to compute a quantized coefficient; reference numeral 340 denotes zero generating means for generating zero; and reference numeral 350 denotes selecting means for comparing a reading address of the transform coefficient to the quantization means 330 and an effective address detected by the effective address detecting means 320 and selecting a result of computation by the quantization means 320 until the effective address is reached, whereas selecting a zero output from the zero generating means 340 after the effective address is reached.
The operation of the above system will now be described with reference to FIGS. 21 and 22.
The system mentioned in the above literature uses the facts that the transform coefficient after DCT is concentrated at a low degree and that zero need not be quantized. Then, the transform coefficient is preliminarily scanned to obtain an effective range of quantization, and only the elements of the transform coefficient falling within the effective range are subjected to quantization, thereby reducing an amount of computation for quantization to attain a high-speed operation of quantization.
For example, prior to performing the quantization, the elements of the transform coefficient are scanned in the order reverse to a conventional scanning order called zigzag scan, and the number of scans until first detection of a non-zero coefficient is set as a maximum degree meaning the effective address. Then, the remaining elements subsequent to the effective address are not subjected to the quantization, but they are set as all zero, thus performing the quantization processing at high speeds.
Specifically in an example of the transform coefficient shown in FIG. 22, first detection of a non-zero coefficient by the reverse zigzag scan is effected at the 39th element in accordance with the order shown in FIG. 2. Accordingly, the remaining elements from the 40th element are not subjected to the quantization, but they are set as zero. Such a zero region thus obtained occupies 37.5% of the whole region, thus resulting in a reduction in processing time to 2/3.
In the transform coefficient obtained by performing DCT to a natural image, most signal power is concentrated at a low-frequency region of the transform coefficient and very small signal power is concentrated at a high-frequency region of the transform coefficient. The conventional system uses this fact and realizes a high-speed operation by omitting the zero region as the high-frequency region from the subject to the quantization.
However, the high-frequency elements of the transform coefficient are not completely zero because of noise in case of inputting an image by the use of a scanner or the like, and some non-zero elements are present though they are small values (see FIG. 10B).
For this reason, the conventional method for deciding an effective range of quantization by determining whether the elements of the transform coefficient after DCT are zero or non-zero as described in the above literature cannot obtain a satisfactory effect of reduction in the effective range. Accordingly, the effect of increase in the operating speed is not satisfactory. Further, since the range of presence of the zero coefficient per block is decided, an additional circuit for detecting zero is required.